class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return  nums[0];
        }
        if(nums.length == 2) {
            return Math.max(nums[0],nums[1]);
        }
        int length = nums.length;
        //第一间和最后一间不可以一起偷，0--length-2。。。。1--length-1。。
        return Math.max(bp(nums,0,length-2),bp(nums,1,length-1));
    }
    public int bp(int[] nums,int start,int end) {
        int dp1 = nums[start];
        int dp2 = Math.max(nums[start],nums[start+1]);
        for(int i = start + 2;i <= end;i++) {
            int tmp = dp2;
            dp2 = Math.max(dp1 + nums[i],dp2);
            dp1 = tmp;
        }
        return dp2;
    }
} 